//
// Created by Incredible on 17/3/22.
//

#ifndef GRAPHTHEORY_SPARSEGRAPH_H
#define GRAPHTHEORY_SPARSEGRAPH_H

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/**
 * 稀疏图 --- 邻接表实现
 *
 */
class SparseGraph {

private:
    int v, e;
    bool directed;


public:
    vector<vector<int>> g;  //邻接表
    //构造函数，传入v --> 节点数； directed --> 是否有向
    SparseGraph(int v, bool directed) {
        this->v = v;
        e = 0;
        this->directed = directed;

        //初始化邻接表
        for (int i = 0; i < v; i++) {
            g.push_back(vector<int>()); //每个邻接表的节点是空的
        }
    }

    ~SparseGraph() {

    }

    int V() {
        return v;
    }

    int E() {
        return e;
    }

    //给两个参数（索引）的代表的顶点添加边
    void addEdge(int a, int b) {

        assert(a >= 0 && a < v);
        assert(b >= 0 && b < v);

        //TODO 判断两顶点是否有边
        if (hasEdge(a, b)) {
            return;
        }
        g[a].push_back(b);

        //判断自环边&&是否有向
        if (a != b && !directed) {
            g[b].push_back(a);
        }
        e++;
    }

    //判断两个顶点是否有边，需要没有顶点的邻接数组，并判断是否有边
    bool hasEdge(int a, int b) {
        assert(a >= 0 && a < v);
        assert(b >= 0 && b < v);

        //O(n)时间复杂度
        for (int i = 0; i < g[a].size(); ++i) {
            if (b == g[a][i]) {
                return true;
            }
        }
        return false;
    }

    void show() {
        //输出v个结点的临界顶点
        for (int i = 0; i < v; i++) {
            cout << "vertex " << i << " :\t ";
            for (int j = 0; j < g[i].size(); ++j) {
                cout << g[i][j] << "\t";
            }
            cout << endl;
        }
    }

    //实现订点的迭代器
    class adjIterator {
    private:
        SparseGraph &G;     //需要遍历的图
        int a;   //需要遍历的顶点
        int index = 0;  //迭代器的下标

    public:

        //构造方法， 参数：需要迭代的图，需要迭代的顶点
        adjIterator(SparseGraph &sparseGraph, int a) : G(sparseGraph) {
            this->a = a;
            index = 0;
        }

        //开始迭代位置
        int begin() {

            //重复调用时清0 下标
            index = 0;

            if (G.g[a].size()) {
                return G.g[a][index];
            }
            return -1;
        }

        //下一个迭代位置
        int next() {
            index++;
            if (G.g[a].size()) {
                return G.g[a][index];
            }
            return -1;
        }

        //判断是否迭代到头
        bool end() {
            return index >= G.g[a].size();
        }
    };
};

#endif //GRAPHTHEORY_SPARSEGRAPH_H










